/* 1. 代码随想录 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 int maxDepth = -1;  // 当前最大深度，全局变量
 int bottomLeftVal;  // 最底层最左值，全局变量
 
 // 递归函数，遍历整棵树
 void traversal(struct TreeNode* root, int depth) {
     if (root == NULL) return;
 
     // 如果是叶子节点
     if (root->left == NULL && root->right == NULL) {
         // 若当前深度比记录的更深，则更新最左值
         if (depth > maxDepth) {
             maxDepth = depth;
             bottomLeftVal = root->val;
         }
         return;
     }
 
     // 先遍历左子树
     traversal(root->left, depth + 1);
     // 再遍历右子树
     traversal(root->right, depth + 1);
 }
 
 // 主函数接口
 int findBottomLeftValue(struct TreeNode* root) {
     maxDepth = -1;  // 初始化最大深度
     bottomLeftVal = 0;
     traversal(root, 0);  // 从根节点开始，深度为 0
     return bottomLeftVal;
 }
 

 /* 2. 20250415 */

/*
    解题思路：
    1. 使用先序遍历（根 -> 左 -> 右），记录当前遍历深度；
    2. 每当遍历到更深的一层（即 curDepth > maxDepth）时，更新左下角的值；
    3. 因为是先访问左子树，所以第一次达到最大深度的一定是最左侧的节点；
*/

typedef struct TreeNode TreeNode;

int maxDepth;     // 当前已知的最大深度
int leftValue;    // 最底层最左侧的节点值

// step 1# 递归函数：遍历整棵树，同时记录深度
void getLeftValue(TreeNode *curNode, int curDepth) {
    // step 2# 如果当前深度超过历史最大深度，更新左下角节点值
    if (curDepth > maxDepth) {
        leftValue = curNode->val;  // 更新最左值
        maxDepth = curDepth;       // 更新最大深度
    }

    // step 3# 先遍历左子树，确保“最左优先”
    if (curNode->left != NULL) getLeftValue(curNode->left, curDepth + 1);

    // step 4# 再遍历右子树
    if (curNode->right != NULL) getLeftValue(curNode->right, curDepth + 1);

    return;
}

// step 5# 主函数，初始化最大深度，启动 DFS
int findBottomLeftValue(struct TreeNode* root) {
    maxDepth = -1;            // 初始深度设为 -1，保证根节点会被记录
    getLeftValue(root, 0);    // 从根节点开始 DFS，深度从 0 开始
    return leftValue;         // 返回记录下来的最底层最左值
}
